// Problem 204: Generalised Hamming Numbers
//
// A Hamming number is a positive number which has no prime factor larger than 5.
// So the first few Hamming numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15.
// There are 1105 Hamming numbers not exceeding 10^8.
// We will call a positive number a generalised Hamming number of type n, if it has no prime factor larger than n.
// Hence the Hamming numbers are the generalised Hamming numbers of type 5.
// How many generalised Hamming numbers of type 100 are there which don't exceed 10^9?

package main

import (
	"fmt"
	"projecteuler/euler"
)

var limit204 = 1000000000

func p204() {
	var ans int = 0
	find204(1, 0, &ans)
	fmt.Println("Problem 204:", ans)
}

func find204(val, idx int, ans *int) {
	if idx > 24 || val > limit204 {
		return
	}
	if idx == 24 && val <= limit204 {
		*ans++
	}
	// pick or not
	find204(val*euler.PrimeList[idx], idx, ans)
	find204(val, idx+1, ans)
}
